package com.itheima.algorithm.sort;

import java.util.Arrays;

// 单边循环快排
public class QuickSortLomuto {

    public static void sort(int[] a) {
        quick(a,0,a.length - 1);
    }

    private static void quick(int [] a,int left,int right) {
        if (left >= right) {
            return;
        }
        int p = partition(a,left,right);
        quick(a,left,p-1);
        quick(a,p+1,right);
    }

    private static int partition(int[] a,int left,int right) {
        int pv = a[right]; // 一开始以数组最右边元素作为基准点元素
        int i = left; // i寻找比基准点大的元素
        int j = left; // j寻找比基准点小的元素
        while (j < right) {
            if (a[j] < pv) { // 找到比基准点小的元素
                if (i != j){
                    swap(a,i,j);
                }
                i++; // 当前找到的元素比基准点小，i就跟着j移动，等找到大的的时候就不移动了
            }
            j++;
        }
        swap(a,i,right);
        return i;
    }

    private static void swap(int [] a,int i,int j){
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

    public static void main(String[] args) {
         int[] a = {5,3,7,2,9,8,1,4};
        System.out.println(Arrays.toString(a));
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}
